package me.eg.ten;

import java.util.Random;

/**
 * 1206. 设计跳表
 * <p>
 * 不使用任何库函数，设计一个跳表。
 * <p>
 * 跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
 * <p>
 * 例如，一个跳表包含 [30, 40, 50, 60, 70, 90]，然后增加 80、45 到跳表中，以下图的方式操作：
 * <p>
 * <p>
 * Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
 * <p>
 * 跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。
 * <p>
 * 在本题中，你的设计应该要包含这些函数：
 * <p>
 * bool search(int target) : 返回target是否存在于跳表中。
 * void add(int num): 插入一个元素到跳表。
 * bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
 * 了解更多 : https://en.wikipedia.org/wiki/Skip_list
 * <p>
 * 注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
 * <p>
 * 约束条件:
 * 0 <= num, target <= 20000
 * 最多调用 50000 次 search, add, 以及 erase操作。
 * <p>
 * 链接：https://leetcode-cn.com/problems/design-skiplist
 */
public class Skiplist {
    private SkipNode head;
    private int level;
    private int size;

    public Skiplist() {
        head = new SkipNode(-1);
        level = 1;
        size = 1;
    }

    public boolean search(int target) {
        SkipNode cur = head;
        while (cur != null) {
            while (cur.next != null && cur.next.val < target) cur = cur.next;
            if (cur.next != null && cur.next.val == target) return true;
            cur = cur.nextLevel;
        }
        return false;
    }

    public void add(int num) {
        SkipNode cur = head;
        SkipNode[] levelNodes = new SkipNode[level];
        int i = 0;
        while (cur != null) {
            while (cur.next != null && cur.next.val < num) cur = cur.next;
            levelNodes[i++] = cur;
            cur = cur.nextLevel;
        }

        cur = levelNodes[--i];
        SkipNode newNode = new SkipNode(num);
        newNode.next = cur.next;
        cur.next = newNode;
        size++;

        addLevelByRandom(newNode, levelNodes, i);
    }

    public boolean erase(int num) {
        boolean isExist = false;
        SkipNode cur = head;
        while (cur != null) {
            while (cur.next != null && cur.next.val < num) cur = cur.next;

            SkipNode next = cur.next;
            if (next != null && next.val == num) {
                cur.next = next.next;
                next.next = null;
                isExist = true;
            }

            cur = cur.nextLevel;
        }
        return isExist;
    }

    private void addLevelByRandom(SkipNode target, SkipNode[] nodes, int curLevel) {
        SkipNode nextLevelNode = target;
        Random random = new Random();
        int rnt = random.nextInt(2);
        while (rnt == 1 && level < (size >> 6)) {
            if (curLevel > 0) {
                SkipNode prev = nodes[--curLevel];
                SkipNode newNode = new SkipNode(target.val);
                newNode.next = prev.next;
                newNode.nextLevel = nextLevelNode;
                prev.next = newNode;

                nextLevelNode = newNode;
                rnt = random.nextInt(2);
            } else {
                SkipNode newNode = new SkipNode(target.val);
                newNode.nextLevel = nextLevelNode;
                SkipNode newHead = new SkipNode(-1);
                newHead.next = newNode;
                newHead.nextLevel = head;
                head = newHead;
                level++;
            }
        }
    }

    class SkipNode {
        private int val;
        private SkipNode next;
        private SkipNode nextLevel;

        public SkipNode(int val) {
            this.val = val;
        }
    }
}